The olfactomedin 4 (OLFM4) gene has been analyzed as a tumor-suppressor gene and a putative biomarker in many cancers. In our study, we analyzed the relationship of OLFM4 expression with clinicopathological features and with CpG site methylation in the OLFM4 gene promoter region in human primary prostate adenocarcinoma. OLFM4 protein expression was significantly reduced in prostate cancer tissue compared to adjacent normal tissue and was further significantly reduced in more advanced cancers. Bioinformatic studies with clinical datasets revealed that primary prostate adenocarcinoma patients with reduced OLFM4 mRNA expression exhibited higher Gleason scores and higher preoperative serum prostate-specific antigen levels, as well as lower recurrence-free survival. Three of the eight CpG sites in the OLFM4 gene promoter region were hypermethylated in cancerous prostate cells compared to adjacent normal cells, and reduced methylation of eight CpG sites was associated with increased OLFM4 mRNA expression in RWPE1 and PC-3 cells. Furthermore, knockdown of OLFM4 gene expression was associated with enhanced epithelial-mesenchymal transition (EMT)-marker expression in RWPE immortalized normal prostate cells. In contrast, restoration of OLFM4 expression in PC-3 and DU145 prostate cancer cells lacking OLFM4 significantly inhibited both EMT-marker expression and tumor cell growth in in vitro and in vivo models, indicating that OLFM4 may play a tumor-suppressor role in inhibiting the EMT program, as well as tumor initiation and growth, in prostate cells. Taken together, these findings suggest that OLFM4 plays an important tumor-suppressor role in prostate cancer progression and might be useful as a novel candidate biomarker for prostate cancer.